package 动态规划;

import org.junit.Test;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/17 9:48
 */
public class leetcode1513仅包含1的子串数 {
    /*
     ==
     该题 可以 使用动态规划, 但是 时间复杂度 O(N ^ 2)
     过不了的, 也别他妈 往动态规划, 上面套了, 该题就不适合 dp

     === 所以直接采用下面的方式
     这尼玛, 也能称作 中等题!
     */
    public int numSub(String s) {
        long count = 0,sum = 0,MOD = 1000000007;
        for(char ch : s.toCharArray()){
            if(ch == '0'){
                sum += (count + 1) * count >> 1;
                sum %= MOD;
                count = 0;
            }else{
                count++;
            }
        }
        sum += count == 0 ? 0 : (count + 1) * count >> 1;
        return (int)(sum %MOD);
    }


    @Test
    public void test(){
        String s = "0110111";
        int i = numSub(s);
    }

}
